import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/5/31.
 *  给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

 示例 1:

 输入: S = "loveleetcode", C = 'e'
 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
 说明:

 字符串 S 的长度范围为 [1, 10000]。
 C 是一个单字符，且保证是字符串 S 里的字符。
 S 和 C 中的所有字母均为小写字母。
 *
 * 索引
 */
public class ShortestDistanceToACharacter {

    public static void main(String[] args) {
        int[] distances = new ShortestDistanceToACharacter().shortestToChar("loveleetcode", 'e');
        for (int distance : distances) {
            System.out.print(distance + ", ");
        }
    }

    public int[] shortestToChar(String S, char C) {
        if (S == null || !S.contains(String.valueOf(C))) {
            return null;
        }

        int[] distances = new int[S.length()];

        // 查找出目标字符出现的所有位置
        List<Integer> targetCharPositions = new ArrayList<>();
        String cs = String.valueOf(C);
        int index = 0;
        while ((index = S.indexOf(cs, index)) != -1 ) {
            targetCharPositions.add(index);
            if (index == S.length() - 1) {
                break;
            }
            index++;
        }

        if (targetCharPositions.isEmpty()) {
            return null;
        }

        int lastTargetOffset = 0;
        int lastTargetPosition = targetCharPositions.get(lastTargetOffset);
        for (int i = 0, size = S.length(); i < size; ++i) {
            if (i < lastTargetPosition) {
                distances[i] = lastTargetPosition - i;
            } else if (i == lastTargetOffset) {
                distances[i] = 0;
            } else if (i > lastTargetOffset && lastTargetOffset == targetCharPositions.size() - 1) {
                distances[i] = i - lastTargetPosition;
            } else if (targetCharPositions.get(lastTargetOffset + 1)  - i > i - lastTargetPosition ){
                distances[i] = i - lastTargetPosition;
            } else {
                lastTargetOffset++;
                lastTargetPosition = targetCharPositions.get(lastTargetOffset);
                distances[i] = lastTargetPosition - i;
            }
        }

        return distances;
    }
}


